<?php
// build the category tree
	
class category_tree{
	
	public $children;	
	public $category_name;
	public $url_list;
	public $url_count;
	
	function __construct(){
		$this->children = array();
		$this->url_list = array();
		$this->category_name = "/";
		$this->url_count=0;
	}
	
	function add_child($tag,$url){
		$new_child = new category_tree();
		$new_child->set_name($tag);
		$new_child->add_url($url);
		$this->children[strtolower($tag)] = $new_child;
		return $this->children[strtolower($tag)];	
	}
	
	function add_url($url){
		array_push($this->url_list,urlencode($url));
		$this->url_count++;
	}
	
	function has_url($url){
		return in_array(urlencode($url),$this->url_list);
	}
	
	function set_name($name){
		$this->category_name = strtolower($name);
	}
	
	function has_child($tag){
		return array_key_exists(strtolower($tag),$this->children);
	}
	
	function get_child($tag,$url){
		if($this->has_child($tag)){
			$child = $this->children[strtolower($tag)];
			if($child->has_url($url)){
				return $child;
			}
			else{
				$child->add_url($url);
				return $child;
			}
		}
		else return $this->add_child($tag,$url);
	}
	
	function add_list($str,$url){
		$arr = explode('/',$str);
		$current = $this->get_child($arr[0],$url);
		$str = $arr[0];
		for($i=1; $i<count($arr);$i++){
			$str = $str."/".$arr[$i];
			$current = $current->get_child($str,$url);
		}
	}
	
	function find_child($tag){
		if($this->category_name == strtolower($tag))
			return $this;
		elseif(count($this->children)<1){
			return null;
		}
		else{
			foreach($this->children as $child){
				if($child->find_child($tag)!=null)
					return $child->find_child($tag);
			}
			return null;
		}
	}
	
	function scan(){
		if(count($this->children)==0){ 
			return $this->category_name;
		}
		if(count($this->children)==1){
			$str = $this->category_name;
			$child = array_pop($this->children);
			$str = $str.",".$child->scan();
			return $str;
		}
		$temp = array();
		foreach($this->children as $child){
			array_push($temp, $child->scan());
		}
		return $this->category_name."{".implode(";", $temp)."}";
	}
	
	
	
	static function find_category_url($node,$max){
		$category_array = array();
		//echo "<br/>name: ".$node->category_name.", children number:".count($node->children).", url_count: ".$node->url_count;
		//print_r($node->url_list);
		//echo "<br/>";
		if($node->url_count<=$max && $node->url_count>0){
			$curr = $node->url_count;
			while(count($node->children)==1){
				$child = array_pop($node->children);
				if($child->url_count==$curr)
					$node = $child;
				else break;
			}
			array_push($category_array,$node);
		}
		else{
			if(count($node->children)<1){
				array_push($category_array,$node);
			}
			else{
				foreach($node->children as $child){
					$temp = category_tree::find_category_url($child,$max);
					$category_array = array_merge($category_array, $temp);
				}
			}
		}
		return $category_array;
	}
	
	
}




/*
$directory = new category_tree();
$directory->add_list("Top/Business/Arts_and_Entertainment/Photography/Tools_and_Equipment/Cameras","zhaiziming.com");
$directory->add_list("Top/Arts/Photography/Equipment_and_Services/Cameras/35mm/Canon","sm.com");
$directory->add_list("Top/Regional/Asia/Japan/Business_and_Economy/Industrial/Manufacturing","nikon.com");

$arr = category_tree::find_category_url($directory,4);
echo count($arr);

foreach( $arr as $child){
	echo "<br/>";
	echo $child->scan();
	echo "<br/>";
}
*/
//echo($directory->scan());

?>